1. Field of the Invention
This invention relates to computer systems and more particularly to arithmetic computations performed therein useful in cryptographic applications.
2. Description of the Related Art
Internet standards such as Secure Socket Layer (SSL) and IP security (IPsec) rely on public-key cryptosystems for scalable key management. With the enormous growth of the World-Wide-Web and, in particular, the ever increasing deployment of e-commerce applications based on https (http over SSL), it has become important to efficiently support cryptographic computations in computer systems, particularly server systems.
Public-key cryptosystems such as the Rivest-Shamir-Adleman (RSA) public-key algorithm and the Diffie-Hellman (DH) key exchange scheme require modular exponentiation with operands of at least 512 bits. Modular exponentiation is computed using a series of modular multiplications and squarings. A newly standardized public-key system, the Elliptic Curve Cryptography (ECC), also uses large integer arithmetic, even though it requires much smaller key sizes. The Elliptic Curve public-key cryptographic systems operate in both integer and binary polynomial fields. A typical RSA operation requires a 1024-bit modular exponentiation (or two 512-bit modular exponentiations using the Chinese Remainder Theorem). RSA key sizes are expected to grow to 2048 bits in the near future. A 1024-bit modular exponentiation includes a sequence of large integer modular multiplications; each, in turn, is further broken up into many word-size multiplications. In total, a 1024-bit modular exponentiation requires over 1.6 million 64-bit multiplications. Thus, public-key algorithms are compute-intensive with relatively few data movements. The computations required are generic arithmetic functions such as integer multiplications and additions. Given those characteristics, public-key algorithms can be well supported by general-purpose processors.
In order to better support cryptography applications, it would be desirable to enhance the capability of general-purpose processors to accelerate public-key computations.